import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/10/9 下午 04:57
 */
public class day191009 {

    public int minCostToMoveChips(int[] chips) {
        int count = 0;
        for (int chip : chips) {
            count += chip % 2;
        }
        return Math.min(count, chips.length - count);
    }


    public int longestSubsequence(int[] arr, int difference) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] += 10000;
        }
        int[] map = new int[20010];
        int[] find = new int[arr.length + 1];
        int ret = 1;
        for (int i = 1; i <= arr.length; i++) {
            int x = arr[i - 1] - difference;
            if (x >= 0 && x <= 20000) {
                find[i] = find[map[x]] + 1;
            } else {
                find[i] = 1;
            }
            ret = Math.max(ret, find[i]);
            map[arr[i - 1]] = i;
        }
        return ret;
    }

    public int getMaximumGold(int[][] grid) {
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                ans = Math.max(ans, dfs(grid, i, j));
            }
        }
        return ans;
    }

    private int dfs(int[][] map, int x, int y) {
        if (x < 0 || x >= map.length || y < 0 || y >= map[0].length || map[x][y] == 0) {
            return 0;
        }
        int cur = map[x][y];
        map[x][y] = 0;
        int ans = cur + Math.max(Math.max(dfs(map, x + 1, y), dfs(map, x - 1, y)), Math.max(dfs(map, x, y + 1), dfs(map, x, y - 1)));
        map[x][y] = cur;
        return ans;
    }


    public int countVowelPermutation(int n) {
        int mod = (int) 1e9 + 7;
        int[][] dp = new int[n + 1][5];
        for (int j = 0; j < 5; j++) {
            dp[1][j] = 1;
        }
        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][1];
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
            dp[i][2] = ((dp[i - 1][0] + dp[i - 1][1]) % mod + (dp[i - 1][3] + dp[i - 1][4]) % mod) % mod;
            dp[i][3] = (dp[i - 1][2] + dp[i - 1][4]) % mod;
            dp[i][4] = dp[i - 1][0];
        }
        return (int) (((long) dp[n][0] + (long) dp[n][1] + (long) dp[n][2] + (long) dp[n][3] + (long) dp[n][4]) % mod);
    }

    public static void main(String[] args) {
        day191009 day191009 = new day191009();
        int[][] queue = new int[][]{{0, 0}, {1, 1}, {2, 2}, {3, 4}, {3, 5}, {4, 4}, {4, 5}};
        day191009.queensAttacktheKing(queue, new int[]{3, 3});
//        System.out.println(day191009.longestSubsequence(new int[]{1, 5, 7, 8, 5, 3, 4, 2, 1}, -2));
    }


    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        int[][] maps = new int[8][8];
        for (int[] queen : queens) {
            maps[queen[0]][queen[1]] = 1;
        }
        List<List<Integer>> ret = new ArrayList<>();
        findQueue(maps, 0, 1, king[0], king[1], ret);
        findQueue(maps, 1, 0, king[0], king[1], ret);
        findQueue(maps, 1, 1, king[0], king[1], ret);
        findQueue(maps, -1, 0, king[0], king[1], ret);
        findQueue(maps, 0, -1, king[0], king[1], ret);
        findQueue(maps, -1, -1, king[0], king[1], ret);
        findQueue(maps, -1, 1, king[0], king[1], ret);
        findQueue(maps, 1, -1, king[0], king[1], ret);
        return ret;
    }

    private void findQueue(int[][] maps, int x, int y, int kx, int ky, List<List<Integer>> ret) {
        int xc = kx + x;
        int yc = ky + y;
        if (xc > 8 || yc > 8 || xc < 0 || yc < 0) {
            return;
        }
        if (maps[xc][yc] == 1) {
            ret.add(Arrays.asList(xc, yc));
            return;
        }
        findQueue(maps, x, y, xc, yc, ret);
    }

    public int balancedStringSplit(String s) {
        int ret = 0;
        if (s.length() == 1) {
            return 0;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char charAt = s.charAt(i);
            if (stack.isEmpty()) {
                stack.add(charAt);
                ret++;
            } else {
                if (stack.peek().equals(charAt)) {
                    stack.add(charAt);
                } else {
                    stack.pop();
                }
            }
        }
        return ret;
    }

    public int dieSimulator(int n, int[] rollMax) {
        int mod = (int) 1e9 + 7;
        int[][][] dp = new int[5050][7][20];
        dp[0][0][0] = 1;
        //掷的次数
        for (int i = 0; i < n; ++i) {
            //点数
            for (int j = 0; j <= 6; ++j) {
                //最多连续出现次数
                for (int k = 0; k <= 15; ++k) {
                    for (int t = 1; t <= 6; ++t) {
                        if (j == t && k + 1 <= rollMax[t - 1]) {
                            dp[i + 1][t][k + 1] += dp[i][j][k];
                            dp[i + 1][t][k + 1] %= mod;
                        } else if (j != t) {
                            dp[i + 1][t][1] += dp[i][j][k];
                            dp[i + 1][t][1] %= mod;
                        }
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 0; i <= 6; ++i) {
            for (int j = 0; j <= 15; ++j) {
                ans += dp[n][i][j];
            }
        }
        ans %= mod;
        return (int) ans;
    }

    public int maxEqualFreq(int[] nums) {
        int ans = 1;
        int max = 0;
        int maxCount = 0;
        int oneCount = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            int c = map.get(nums[i]);
            if (c == max) {
                ++maxCount;
            } else if (c > max) {
                max = c;
                maxCount = 1;
            }
            if (c == 1) {
                ++oneCount;
            } else if (c == 2) {
                --oneCount;
            }
            if (i == 21) {
                System.out.println(max + " " + maxCount + " " + oneCount);
            }
            if (oneCount > 0 && (max * (map.size() - 1)) == i) {
                ans = i + 1;
            }
            if (maxCount == 1 && (max - 1) * map.size() == i) {
                ans = i + 1;
            }
        }
        return ans;
    }
}
